package com.cty.eleventhDay;

import java.util.Arrays;

/*
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
 *
 * */
public class Q_13 {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int res = maxSubArray2(nums);
        System.out.println(res);
    }

    //力扣官方题解 贪心 记录前一个序列的和 如果小于0 则抛弃大于零相加 时间复杂度O(n) 空间复杂度O(1)
    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length, maxSum = Integer.MIN_VALUE, currentSum = 0, preSum = 0;
        for (int i = 0; i < n; i++) {
            // 如果前一个序列的和大于0则相加 如果小于等于0则抛弃
            if (preSum > 0) {
                currentSum = preSum + nums[i];
            } else {
                currentSum = nums[i];
            }
            maxSum = Math.max(currentSum, maxSum);
            preSum = currentSum;
        }
        return maxSum;
    }

    //力扣官方题解 动态规划 如果前一个元素的值大于0 就加到本元素上小于等于零就保持本元素 时间复杂度O(n) 空间复杂度O(1)
    public static int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            if (nums[i - 1] > 0) {
                // 如果上一个元素大于0就加上上一个元素 (动态规划的中心思想)
                nums[i] += nums[i - 1];
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i< n;i++) {
            max = Math.max(max,nums[i]);
        }
        return max;
    }
}
